package 剑指Offer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Offer59II_队列的最大值 {

    class MaxQueue {
        private Queue<Integer> queue;
        private Deque<Integer> deque;//用来维护一个递减队列，便于快速找到最大值

        public MaxQueue() {
            queue = new LinkedList<>();
            deque = new LinkedList<>();
        }

        public int max_value() {
            //deque的首元素就是最大值
            return deque.isEmpty() ? -1 : deque.peekFirst();
        }

        public void push_back(int value) {
            queue.offer(value);
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast();
            }
            deque.offerLast(value);
        }


        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            //弹出的是最大值则两个都需要更新
            if (queue.peek().equals(deque.peekFirst())) {
                deque.pollFirst();
            }
            return queue.poll();
        }
    }
}
